{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quantum Appromaxiate Optimization Algorithm Tutorial\n",
    "\n",
    "## Introduction\n",
    "QAOA is a kind of quantum algorithm which can solve combinatorial optimization problem, for example, optimal partition problem. Here we show an example of QAOA."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pyqpanda.Hamiltonian import PauliOperator\n",
    "from pyqpanda.Hamiltonian.QubitOperator import *\n",
    "from pyqpanda import *\n",
    "from pyqpanda.utils import *\n",
    "from pyqpanda.Algorithm.hamiltonian_simulation import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Description\n",
    "First, we construct a graph  *G* which represents the optimal problem, codes *[i,j,C<sub>ij]* means the weight of edge *G<sub>ij* is *w*. The problem is finding a partition which divides *G* into $ G_1 $ and $ G_2 $ and makes the *SUM* is maximal,where *SUM* is defined as:\n",
    "$$ SUM= \\sum_{i\\in G_1,j\\in G_2} C_{ij} $$  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#define graph\n",
    "graph=[[0,5,0.18],[0,6,0.49],[1,6,0.59],[1,7,0.44],\\\n",
    "[2,7,0.56],[2,8,0.63],[4,9,0.43],[5,10,0.23],[6,11,0.64],\\\n",
    "[7,12,0.60],[8,13,0.36],[9,14,0.52],[10,15,0.40],[10,16,0.41],\\\n",
    "[11,16,0.57],[11,17,0.50],[12,17,0.71],[12,18,0.40],[13,18,0.72],\\\n",
    "[13,3,0.81],[14,3,0.29]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Target Hamiltonian\n",
    "\n",
    "$$ H_c=-\\frac{1}{2}\\sum_{ij}C_{ij}(1-\\sigma_i^z\\sigma_j^z)  $$ \n",
    "Construct quantum circuit of $ e^{-i\\gamma H_c} $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#QUBITS_NUM 19\n",
      "#CREGS_NUM 0\n",
      "CNOT 0,5\n",
      "RZ 5,\"0.036000\"\n",
      "CNOT 0,5\n",
      "CNOT 0,6\n",
      "RZ 6,\"0.098000\"\n",
      "CNOT 0,6\n",
      "CNOT 1,6\n",
      "RZ 6,\"0.118000\"\n",
      "CNOT 1,6\n",
      "CNOT 1,7\n",
      "RZ 7,\"0.088000\"\n",
      "CNOT 1,7\n",
      "CNOT 2,7\n",
      "RZ 7,\"0.112000\"\n",
      "CNOT 2,7\n",
      "CNOT 2,8\n",
      "RZ 8,\"0.126000\"\n",
      "CNOT 2,8\n",
      "CNOT 4,9\n",
      "RZ 9,\"0.086000\"\n",
      "CNOT 4,9\n",
      "CNOT 5,10\n",
      "RZ 10,\"0.046000\"\n",
      "CNOT 5,10\n",
      "CNOT 6,11\n",
      "RZ 11,\"0.128000\"\n",
      "CNOT 6,11\n",
      "CNOT 7,12\n",
      "RZ 12,\"0.120000\"\n",
      "CNOT 7,12\n",
      "CNOT 8,13\n",
      "RZ 13,\"0.072000\"\n",
      "CNOT 8,13\n",
      "CNOT 9,14\n",
      "RZ 14,\"0.104000\"\n",
      "CNOT 9,14\n",
      "CNOT 10,15\n",
      "RZ 15,\"0.080000\"\n",
      "CNOT 10,15\n",
      "CNOT 10,16\n",
      "RZ 16,\"0.082000\"\n",
      "CNOT 10,16\n",
      "CNOT 11,16\n",
      "RZ 16,\"0.114000\"\n",
      "CNOT 11,16\n",
      "CNOT 11,17\n",
      "RZ 17,\"0.100000\"\n",
      "CNOT 11,17\n",
      "CNOT 12,17\n",
      "RZ 17,\"0.142000\"\n",
      "CNOT 12,17\n",
      "CNOT 12,18\n",
      "RZ 18,\"0.080000\"\n",
      "CNOT 12,18\n",
      "CNOT 13,18\n",
      "RZ 18,\"0.144000\"\n",
      "CNOT 13,18\n",
      "CNOT 13,3\n",
      "RZ 3,\"0.162000\"\n",
      "CNOT 13,3\n",
      "CNOT 14,3\n",
      "RZ 3,\"0.058000\"\n",
      "CNOT 14,3\n",
      "\n"
     ]
    }
   ],
   "source": [
    "#decide qubit number\n",
    "qn_=get_qn_from_graph(graph)\n",
    "init()\n",
    "prog=QProg()\n",
    "q=qAlloc_many(qn_)\n",
    "prog.insert(ising_model(q,graph,0.1))\n",
    "print(to_qrunes(prog))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Driver Hamiltonian $$ H_d=\\sum_{i}\\sigma_i^x  $$ \n",
    "construct quantum circuit of $$ e^{-i\\beta H_d} $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#QUBITS_NUM 19\n",
      "#CREGS_NUM 0\n",
      "RX 0,\"1.000000\"\n",
      "RX 1,\"1.000000\"\n",
      "RX 2,\"1.000000\"\n",
      "RX 3,\"1.000000\"\n",
      "RX 4,\"1.000000\"\n",
      "RX 5,\"1.000000\"\n",
      "RX 6,\"1.000000\"\n",
      "RX 7,\"1.000000\"\n",
      "RX 8,\"1.000000\"\n",
      "RX 9,\"1.000000\"\n",
      "RX 10,\"1.000000\"\n",
      "RX 11,\"1.000000\"\n",
      "RX 12,\"1.000000\"\n",
      "RX 13,\"1.000000\"\n",
      "RX 14,\"1.000000\"\n",
      "RX 15,\"1.000000\"\n",
      "RX 16,\"1.000000\"\n",
      "RX 17,\"1.000000\"\n",
      "RX 18,\"1.000000\"\n",
      "\n"
     ]
    }
   ],
   "source": [
    "progx=QProg()\n",
    "beta=0.5\n",
    "progx.insert(pauliX_model(q,beta))\n",
    "print(to_qrunes(progx))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## QAOA quantum program generation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-8.64\n"
     ]
    }
   ],
   "source": [
    "gamma=[0.5,-0.5]\n",
    "beta=[0.5,-0.5]\n",
    "result=quantum_approximate_optimization_algorithm(\n",
    "    graph,\n",
    "    gamma,\n",
    "    beta,\n",
    "    use_prob_run=True,\n",
    "    use_quick_measure=True,\n",
    "    multiProcessing=False,    \n",
    "    shots_=100, \n",
    "    dataType=\"list\")\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## QAOA quantum program execution\n",
    "parameter optimization of QAOA and print the optimized parameter.\n",
    "result.x is sequence of optimized parameter\n",
    "qaoa.txt:save optimization process data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.5, 0.5, -0.5, -0.5] initial guess\n",
      "   direc: array([[1., 0., 0., 0.],\n",
      "       [0., 1., 0., 0.],\n",
      "       [0., 0., 1., 0.],\n",
      "       [0., 0., 0., 1.]])\n",
      "     fun: array(-7.27)\n",
      " message: 'Optimization terminated successfully.'\n",
      "    nfev: 63\n",
      "     nit: 1\n",
      "  status: 0\n",
      " success: True\n",
      "       x: array([ 1.41881793,  0.47680084, -0.25510086, -4.01263051])\n"
     ]
    }
   ],
   "source": [
    "step=2\n",
    "f=open(\"qaoa.txt\", 'w')\n",
    "f.close()\n",
    "gamma_=[]\n",
    "beta_=[]\n",
    "shots=1\n",
    "for i in range(step):\n",
    "    gamma_.append(0.5)\n",
    "    beta_.append(-0.5)\n",
    "initial_guess=gamma_+beta_\n",
    "print(initial_guess,'initial guess')\n",
    "#Scipy.optimize.minize function as optimize funciton\n",
    "result = minimize(binding(graph,shots), initial_guess, method=\"Powell\")\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## *QAOA function*\n",
    "All funciton described above can realized by *\"qaoa\"* function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   direc: array([[1., 0., 0., 0.],\n",
      "       [0., 1., 0., 0.],\n",
      "       [0., 0., 1., 0.],\n",
      "       [0., 0., 0., 1.]])\n",
      "     fun: array(-10.48)\n",
      " message: 'Optimization terminated successfully.'\n",
      "    nfev: 115\n",
      "     nit: 2\n",
      "  status: 0\n",
      " success: True\n",
      "       x: array([ 1.31849533,  3.84878686, -0.68766259,  0.33267957])\n"
     ]
    }
   ],
   "source": [
    "result=qaoa(graph=graph,step_=2,shots_=100, method=\"Powell\")\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
